#include "dllist.h"

DLList createDLList(void)
{
    DLList list;
    list = (DLList) malloc(sizeof(struct dlList));
    if (list == NULL)
    {
        return NULL;
    }
    
    list->head = (PNode) malloc(sizeof(struct DLNode));
    if (list->head == NULL)
    {
        free(list);
        return NULL;
    }
    
    list->head->right = NULL;
    list->head->left = NULL;
    list->rear = list->head;
    list->length = 0;
    
    return list;
}

POSITION locateVertexDLList(DLList list, ELEMTYPE x)
{
    POSITION p;
    
    if (list == NULL)
    {
        return NULL;
    }
    
    p = list->head->right;

    while (p != NULL && p->info != x)
    {
        p = p->right;
    }
   
    #ifdef DEBUG
    if (p != NULL)
    {
        printf("ELEMENT %d is found in this dllist, the address is %u\n", x, p);
    }
    else
    {
        printf("ELEMENT %d is not found in this dllist\n", x);
    }
    #endif

    return p;
}

int insertPostDLList(DLList list, POSITION p, ELEMTYPE x)
{
    PNode q;

    if (list == NULL || p == NULL)
    {
        return 0;
    }

    q = (PNode) malloc(sizeof(struct DLNode));
    
    if (q != NULL)
    {
        q->info = x;
        q->right = p->right;
        q->left = p;
       
        if (q->right != NULL)
        {
            q->right->left = q;
        }

        if (p == list->rear)
        {
            list->rear = q;
        }

        p->right = q;

        list->length++;
        return 1;
    }

    return -1;
}

int insertPreDLList(DLList list, POSITION p, ELEMTYPE x)
{
    PNode q;

    if (list == NULL || p == NULL)
    {
        return 0;
    }

    q = (PNode) malloc(sizeof(struct DLNode));
    
    if (q != NULL)
    {
        q->info = x;

        q->right = p;
        p->left->right = q;

        q->left = p->left;
        p->left = q;

        list->length++;
        return 1;
    }

    return -1;
}

int deleteElemDLList(DLList list, ELEMTYPE x)
{
    PNode p, q;
    #ifdef DEBUG
    SIZE_T i=0;
    int result;
    #endif

    if (list == NULL)
    {
        return -1;
    }
    
    p =  locateVertexDLList(list, x);
    deleteVertexDLList(list, p);
    return 0;
}

int deleteVertexDLList(DLList list, POSITION p)
{
    PNode q;
    #ifdef DEBUG
    SIZE_T i=0;
    #endif

    if (list == NULL)
    {
        return -1;
    }
    
    if (p != NULL)
    {
        #ifdef DEBUG
        printf("\n==================NODE WILL BE DELETED============================\n");
        printf("node[%d]->left = %u, node[%d]->info = %d, node[%d]->right = %u, address = %u\n", i, p->left, i, p->info, i, p->right, p);
        printf("==================NODE WILL BE DELETED============================\n");
        #endif

        if (p == list->rear)
        {
            list->rear = p->left;
        }

        p->left->right = p->right;
        if (p->right != NULL)
        {
            p->right->left = p->left;
        }

        list->length = list->length - 1;
        free(p);
        return 1;
    }

    return 0;
}

int appendElemDLList(DLList list, ELEMTYPE x)
{
    PNode p;

    if (list == NULL)
    {
        return -1;
    }
    
    p = (PNode) malloc(sizeof(struct DLNode));
    
    if (p != NULL)
    {
        p->info = x;
        p->right = list->rear->right;
        p->left = list->rear;

        list->rear->right = p;
        
        list->rear = p;
        list->length++;
        return 1;
    }
    
    return 0;
}

void printDLList(DLList list)
{
    POSITION p;
    SIZE_T i;
    
    if (list == NULL)
    {
        return ;
    }

    #ifdef DEBUG
    printf("\n==================DLLIST============================\n");
    printf("HEAD = %u, REAR = %u, length = %d\n", list->head, list->rear, list->length);
    #endif
    p = list->head->right;
    i = 0;
    #ifdef DEBUG
    i = -1;
    p = list->head;
    printf("\n==================HEAD NODE============================\n");
    printf("node[%d]->left = %u, node[%d]->info = %d, node[%d]->right = %u, address = %u\n", i, p->left, i, p->info, i, p->right, p);
    printf("=====================START=============================\n");
    i++;
    p = list->head->right;
    #endif
    while (p != NULL)
    {
        #ifdef DEBUG
        printf("node[%d]->left = %u, node[%d]->info = %d, node[%d]->right = %u, address = %u\n", i, p->left, i, p->info, i, p->right, p);
        #else
        printf("%d ", p->info);
        #endif

        i++;
        p = p->right;
    }
    #ifdef DEBUG
    printf("======================END=============================\n");
    #else
    printf("\n");
    #endif
}

void destroyDLList(DLList *list)
{
    PNode p, q;

    if (*list == NULL)
    {
        return ;
    }

    p = (*list)->head;

    do {
        q = p;
        p = p->right;
        free(q);
    } while (p != NULL);
/*
    while (p != NULL)
    {
        q = p;
        p = p->link;
        free(q);
    }
*/
    
    free(*list);
    *list = NULL;
}

SIZE_T lengthDLList(DLList list)
{
    if (list != NULL)
    {
        return list->length;
    }
    return -1;
}

POSITION getPositionByIndexDLList(DLList list, SIZE_T index)
{
    POSITION p;
    SIZE_T i, length;
    if (list == NULL)
    { 
        return NULL;
    }
    
    length = lengthDLList(list);
    
    if (index > length)
    {
        return NULL;
    }
    
    for (i = 0, p = list->head->right; i < index; i++)
    {
        p = p->right;
    }
    #ifdef DEBUG
    printf("=============INDEX TO POSITION===========\n");
    printf("Index = %d, POSITION = %u\n", index, p);
    printf("=============INDEX TO POSITION===========\n");
    #endif
    return p;
}

